
/**
*      author: Y_Yao
*      created: 2025-04-12 21:32:46
**/

#include<bits/stdc++.h>

#define int LL
using namespace std;
using LL = long long;
const int N = 1e6 + 7;
const int mod = 1e9;
LL n,k;
int a[N];
int sum[N];

void solve()
{
    cin >> n >> k;
    queue<int> q;
    for(int i = 0;i < k;i++)
    {
        q.push(1);
    }

    if(k >= n + 1)
    {
        cout << 1 << endl;
        return;
    }

    int sum = k;
    for(int i = k;i <= n - 1;i++)
    {
        int in = sum % mod;
        sum = (sum + in) % mod;
        q.push(in);
        auto t = q.front();
        q.pop();
        t = t % mod;
        sum = (sum - t) % mod;
        sum = (sum + mod) % mod;
    }

    cout << sum % mod << endl;

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    while(t--)
    {
        solve();
    }
    return 0;
}

